class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> sta;
        int i = 0;int sum = 0;
        while(i < height.size())
        {
            while(!sta.empty() && height[i] > height[sta.back()])
            {
                int top = sta.back();
                sta.pop_back();
                if(sta.empty())break;
                int instance = i - sta.back() - 1;
                int he = min(height[i],height[sta.back()]) - height[top];
                sum +=he * instance;
            }
            sta.push_back(i++);
        }
        return sum;

    }
};



